﻿namespace LeetCodeProject._0001_1000._001_100._81_90._086;

public class Solution
{
    public ListNode Partition(ListNode head, int x)
    {
        //先把小于x和大于等于x的链表做好，然后在连接起来
        if (head == null)
            return null;
        //左半部分
        ListNode leftHead = new ListNode(0);
        ListNode leftTail = leftHead;

        //右半部分
        ListNode rightHead = new ListNode(0);
        ListNode rightTail = rightHead;
        while (head != null)
        {
            if (head.val < x)
            {
                leftTail.next = head;
                leftTail = head;
            }
            else
            {
                rightTail.next = head;
                rightTail = head;
            }

            head = head.next;
        }

        //原来的链表倒数第N个节点A的值是 >=x的，A后面所有的值都 <x的情况，rightTail.next就是最后的节点，其next为null
        rightTail.next = null;
        //左右部分连接
        leftTail.next = rightHead.next;
        return leftHead.next;
    }
}